package com.hy;

/**
 * Created With IntelliJ IDEA.
 * Descriptions:接雨水
 * 给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
 *
 * 示例 1：
 * 输入：height = [4,2,0,3,2,5]
 *
 * 输出：9
 * User:Mr.Du
 * Date:2023/9/20
 * Time:10:46
 */
public class Trap {

    /**
     * height[i]位置接的水，由它的左边和右边的最大值决定，记lMax和rMax分别为height[i]的最大值，
     * 那么height[i]位置接的水就是min(lMax, rMax) - height[i]
     *
     * @param height
     * @return
     */
    public int trap1(int[] height) {
        int n = height.length, res = 0;
        for(int i = 1;i < n - 1;i++){
            int lMax = 0, rMax = 0;
            for(int j = i;j >= 0;j--){
                lMax = Math.max(height[j], lMax);
            }
            for(int j = i;j < n;j++){
                rMax = Math.max(height[j], rMax);
            }
            res += Math.min(rMax, lMax) - height[i];
        }
        return res;
    }

    /**
     * trap1时间复杂度很高，是因为我们每次都要计算height[i]的左右最大值，
     * 优化：把height[i]的左右最大值提前计算出来
     * 备忘录操作
     * @param height
     * @return
     */
    public int trap2(int[] height) {
        int n = height.length, res = 0;
        int[] numsL = new int[n];
        int[] numsR = new int[n];
        numsL[0] = height[0];
        numsR[n - 1] = height[n - 1];
        for(int i = 1;i < n;i++){
            numsL[i] = Math.max(height[i], numsL[i - 1]);
        }
        for(int i = n - 2;i >= 0;i--){
            numsR[i] = Math.max(height[i], numsR[i + 1]);
        }
        for(int i = 1;i < n - 1;i++){
            res += Math.min(numsL[i], numsR[i]) - height[i];
        }
        return res;
    }

    /**
     * 双指针，没搞懂，后面再看
     * @param height
     * @return
     */
    public int trap3(int[] height) {
        int left = 0, right = height.length - 1;
        int l_max = 0, r_max = 0;
        int res = 0;
        while (left < right) {
            l_max = Math.max(l_max, height[left]);
            r_max = Math.max(r_max, height[right]);
            if (l_max < r_max) {
                res += l_max - height[left];
                left++;
            } else {
                res += r_max - height[right];
                right--;
            }
        }
        return res;
    }

    public static void main(String[] args) {
        Trap trap = new Trap();
        int[] height = {0,1,0,4,1,0,1,6,3,1,2,1};
        int res = trap.trap3(height);
        System.out.println(res);
    }

}
